package algorithm

// lru算法 最少使用淘汰策越
type Lru struct {
	head Element
	tail Element

	capacity int
	used     int
}

// 双指针
type Element struct {
	pre     *Element
	next    *Element
	content string
}

// 新增元素
func (l Lru) put(element Element) {
	filled := l.isFill()

	// 存放新增数据
	old := l.head
	l.head = element
	l.head.pre = nil
	l.head.next = &old
	old.pre = &element

	if filled { // 已占满
		// 淘汰末尾数据
		pre := l.tail.pre

		l.tail = *pre
		l.tail.next = nil
	} else if l.used == 0 { // 未使用
		l.tail = element
		l.tail.next = nil
		l.used = l.used + 1
	} else { // 已使用，但是未占满
		l.used = l.used + 1
	}

}

// 已使用数量
func (l Lru) size() int {
	return l.used
}

// 总共数量
func (l Lru) capacities() int {
	return l.capacity
}

// 是否用满
func (l Lru) isFill() bool {
	if l.capacity > l.used {
		return true
	}
	return false
}
